package com.interview.javabasic.Algorithm;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.Arrays;

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A','B','C','D','E','F','G'};
        int[][] metrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        metrix[0] = new int[]{N,5,7,N,N,N,2};
        metrix[1] = new int[]{5,N,N,9,N,N,3};
        metrix[2] = new int[]{7,N,N,N,8,N,N};
        metrix[3] = new int[]{N,9,N,N,N,4,N};
        metrix[4] = new int[]{N,N,8,N,N,5,4};
        metrix[5] = new int[]{N,N,N,4,5,N,6};
        metrix[6] = new int[]{2,3,N,N,4,6,N};

        Graph graph = new Graph(vertex,metrix);
        graph.showGraph();
        graph.dsj(6);
        graph.showDsj();

    }
}

class Graph{
    private char[] vertex;//顶点数组
    private int[][] metrix;//邻接矩阵
    private VisitedVertex vv;//已经访问的顶点集合
     //构造器
    public Graph(char[] vertex,int[][] metrix){
        this.vertex = vertex;
        this.metrix = metrix;
    }

    public void showDsj(){
        vv.show();
    }

    //显示图
    public void showGraph(){
        for (int[] ints : metrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    //迪杰斯特拉算法实现
    /*index表示出发顶点对应的下标*/
    public void dsj(int index){
        vv = new VisitedVertex(vertex.length, index);
        //更新index顶点到周围顶点的距离和前驱顶点
        update(index);

        for (int i = 1; i < vertex.length; i++) {
            index = vv.updataArr();//选择并返回新的访问顶点
             update(index);
        }


    }

    /*
    * 更新index下标顶点到周围顶点的距离和周围顶点的前驱节点*/
    private void update(int index){
        int len = 0;
        //根据遍历邻接矩阵的index行
        for (int i = 0; i < metrix[index].length; i++) {
            //len含义是：出发顶点到index顶点距离+index顶点到j顶点的距离
            len =  vv.getDis(index) + metrix[index][i];
            if (!vv.in(i) && len < vv.getDis(i)){
                vv.updatePre(i,index);//更新j顶点的前驱节点为index
                vv.updateDis(i,len);//更新
            }
        }
    }
}

class VisitedVertex{
    //记录各个顶点是否访问过，1表示访问过，0表示未访问，会动态更新
    public int[] already_arr;
    //每个下标对应的值为前一个顶点下标，会动态更新
    public int[] pre_visited;
    //记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会即可G到其他顶点的距离
    public int[] dis;
    /*
    * length表示顶点的个数*/
    public VisitedVertex(int length,int index){
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        //初始化dis数组
        Arrays.fill(dis,65535);
        this.already_arr[index] = 1;//设置出发顶点被访问过了。
        this.dis[index] = 0; //设置出发顶点的访问距离为0；
    }
    /*
    * 判断index下标的顶点是否被访问过，
    * 如果被访问过就返回true
    * 否则返回false*/
    public boolean in(int index){
        return already_arr[index]==1;
    }

    /**更新出发顶点，到index顶点的距离
     * index：
     * */
    public void updateDis(int index,int len){
        dis[index] = len;
    }
    /*更新顶点的前驱为index节点*/
    public void updatePre(int pre,int index){
        pre_visited[pre] = index;
    }
    /*返回出发顶点到index顶点的距离*/
    public int getDis(int index){
        return dis[index];
    }
/*继续选择并返回新的访问节点*/
    public int updataArr(){
        int min = 65535, index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i] == 0 && dis[i]<min){
                min = dis[i];
                index = i;
            }
        }
        already_arr[index] = 1;
        return index;
    }

    //显示最后的结果
    public void show(){
        System.out.println("========================");
        for (int i : already_arr) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (int i : pre_visited) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int di : dis) {
            System.out.print(di + " ");
        }
        System.out.println();
        char[] vertex = {'A','B','C','D','E','F','G'};
        int count = 0;
        for (int i : dis) {
            if (i!=65535){
                System.out.print(vertex[count] + "("+i+")");
            }else{
                System.out.println("N");
            }
            count++;
        }
        System.out.println();
    }
}
